﻿// 0820train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;
    TreeNode() = default;
    TreeNode(int val) : val(val) {};
};

TreeNode* BuildNode(vector<int>&tree_vec)
{
    queue<TreeNode*>bfs_queue;
    TreeNode* root = new TreeNode(tree_vec[0]);
    bfs_queue.push(root);

    int index = 1;
    while (!bfs_queue.empty() && index<tree_vec.size())
    {
        TreeNode* top_node = bfs_queue.front();
        bfs_queue.pop();
        if (index<tree_vec.size() && tree_vec[index] != INT_MIN)
        {
            top_node->left = new TreeNode(tree_vec[index]);
            bfs_queue.push(top_node->left);
        }
        index++;
        if (index < tree_vec.size() &&tree_vec[index]!=INT_MIN)
        {
            top_node->right = new TreeNode(tree_vec[index]);
            bfs_queue.push(top_node->right);
        }
        index++;
    }
    return root;
}

/*给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点*/

TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) return root;
    queue<TreeNode*>bfs_queue;
    bfs_queue.push(root);

    while (!bfs_queue.empty())
    {
        TreeNode* top_node = bfs_queue.front();
        bfs_queue.pop();

        TreeNode* left = top_node->left;
        top_node->left = top_node->right;
        top_node->right = left;
        

        if (top_node->left!=nullptr)
        {
            bfs_queue.push(top_node->left);
        }
        if (top_node->right!=nullptr)
        {
            bfs_queue.push(top_node->right);
        }
        
    }
    return root;
    //invertTree
}

/*
 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 */

int minDepth(TreeNode* root)
{
    if (root == nullptr)
        return 0;
    queue<TreeNode*>bfs_queue;
    bfs_queue.push(root);
    int level = 0;
    while (!bfs_queue.empty())
    {
        level++;
        int q_size = bfs_queue.size();
        bool is_find = false;
        for (int i=0; i<q_size; i++)
        {
            TreeNode* top_node = bfs_queue.front();
            bfs_queue.pop();

            if (top_node->left==nullptr&&top_node->right==nullptr)
            {
                is_find = true;
                break;
            }
            if (top_node->left!=nullptr)
            {
                bfs_queue.push(top_node->left);
            }
            if (top_node->right!=nullptr)
            {
                bfs_queue.push(top_node->right);
            }

        }
        if (is_find) break;


    }
    return level;
}


/*
 判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum
 如果存在，返回 true ；否则，返回 false 
 */
bool hasPathSum(TreeNode* root, int targetSum) {
    if (root == nullptr) return false;

    queue<TreeNode*>node_queue;
    queue<int>value_queue;

    node_queue.push(root);
    value_queue.push(root->val);

    bool is_find = false;
    while (!node_queue.empty())
    {
        TreeNode* top_node = node_queue.front();
        node_queue.pop();
        int top_value = value_queue.front();
        value_queue.pop();

        if (top_value==targetSum)
        {
            if (top_node->left==nullptr && top_node->right==nullptr)
            {
                is_find = true;
                break;
            }
        }

        if (top_node->left!=nullptr)
        {
            node_queue.push(top_node->left);
            value_queue.push(top_value + top_node->left->val);
        }

        if (top_node->right!=nullptr)
        {
            node_queue.push(top_node->right);
            value_queue.push(top_value + top_node->right->val);
        }

    }

    return is_find;
    //hasPathSum
}


/*给定二叉树的根节点 root ，返回所有左叶子之和*/
int sumOfLeftLeaves(TreeNode* root) {
    queue<TreeNode*>bfs_queue;
    queue<TreeNode*>left_queue;
    bfs_queue.push(root);
    vector<int>left_leaf_vec;
    int level = 0;
    while (!bfs_queue.empty())
    {
        level++;
        //层序遍历
        int q_size = bfs_queue.size();

        for (int i=0; i<q_size; i++)
        {
            TreeNode* top_node = bfs_queue.front();
            bfs_queue.pop();
            bool is_left = false;

            if (!left_queue.empty()&& top_node == left_queue.front())
            {
                is_left = true;
                left_queue.pop();
            }

            if (is_left &&top_node->left==nullptr && top_node->right==nullptr)
            {
                left_leaf_vec.push_back(top_node->val);
            }

            if (top_node->left!=nullptr)
            {
                bfs_queue.push(top_node->left);
                left_queue.push(top_node->left);
            }
            if (top_node->right!=nullptr)
            {
                bfs_queue.push(top_node->right);
            }

        }
    }
    if (level == 1) return 0;

    int result = 0;
    for (auto&num:left_leaf_vec)
    {
        result += num;
    }
    return result;
    //sumOfLeftLeaves
}


/*如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。*/
bool isUnivalTree(TreeNode* root) {
    if (root == nullptr) return true;
    unordered_set<int>value_set;
    queue<TreeNode*>bfs_queue;
    bfs_queue.push(root);
    value_set.insert(root->val);

    while (!bfs_queue.empty())
    {
        TreeNode* top_node = bfs_queue.front();
        bfs_queue.pop();
        int top_value = top_node->val;

        if (value_set.count(top_value)==0)
        {
            return false;
        }

        if (top_node->left!=nullptr)
        {
            bfs_queue.push(top_node->left);
        }
        if (top_node->right!=nullptr)
        {
            bfs_queue.push(top_node->right);
        }

    }
    return true;

    //------
}


/*给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。*/
bool isSameTree(TreeNode* p, TreeNode* q) {
    if (p == nullptr && q == nullptr) return true;
    if (p == nullptr || q == nullptr) return false;

    queue<TreeNode*>bfs_queue;
    bfs_queue.push(p);
    bfs_queue.push(q);

    while (!bfs_queue.empty())
    {
        TreeNode* p_node = bfs_queue.front();
        bfs_queue.pop();
        TreeNode* q_node = bfs_queue.front();
        bfs_queue.pop();

        if (p_node->val!=q_node->val)
        {
            return false;
        }

        if (p_node->left!=nullptr&& q_node->left != nullptr)
        {
            bfs_queue.push(p_node->left);
            bfs_queue.push(q_node->left);
        }
        else if (p_node->left==nullptr&&q_node->left==nullptr)
        {
        }
    	else
        {
            return false;
        }

        if (p_node->right!=nullptr&& q_node->right != nullptr)
        {
            bfs_queue.push(p_node->right);
            bfs_queue.push(q_node->right);
        }
        else if (p_node->right == nullptr && q_node->right == nullptr)
        {
        }
        else
        {
            return false;
        }
	    
    }
    return true;
}


class Solution01 {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        queue<TreeNode*>node_queue;
        queue<string>path_queue;
        vector<string>result_vec;

        node_queue.push(root);
        string path = to_string(root->val);
        path_queue.push(path);

        while (!node_queue.empty())
        {
            TreeNode* top_node = node_queue.front();
            node_queue.pop();
            string top_path = path_queue.front();
            path_queue.pop();

            if (top_node->left==nullptr&&top_node->right==nullptr)
            {
                result_vec.push_back(top_path);
            }
            else
            {
                if (top_node->left!=nullptr)
                {
                    node_queue.push(top_node->left);
                    string new_path = top_path + "->";
                    new_path += to_string(top_node->left->val);
                    path_queue.push(new_path);
                }
                if (top_node->right!=nullptr)
                {
                    node_queue.push(top_node->right);
                    string new_path = top_path + "->";
                    new_path += to_string(top_node->right->val);
                    path_queue.push(new_path);
                }

            }
	        
        }
        return result_vec;
    }
};

int main()
{
    const int null = INT_MIN;
    vector<int>tree_vec = { 1,2,3,null,5 };
    TreeNode* root = BuildNode(tree_vec);
    //invertTree(root);
    //cout << minDepth(root);
    //int targetSum = 22;
    //Solution01 solu;
    //cout << hasPathSum(root, targetSum);
    //root = [3,9,20,null,null,15,7]
    //p = [1, 2, 3], q = [1, 2, 3]
    //vector<int>p_tree = { 1, 2, 3 };
    //vector<int>q_tree = { 1, 2, 3 };
    //TreeNode* p_root = BuildNode(p_tree);
    //TreeNode* q_root = BuildNode(q_tree);
    //cout << isSameTree(p_root, q_root);
    Solution01 solu;
    vector<string>result = solu.binaryTreePaths(root);
    for (auto&str:result)
    {
        cout << str << endl;
    }

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
